The present invention relates generally to forward error correction (FEC) circuitry and techniques which may be added to an existing digital communication system including a transmitter and a receiver including any CRC (cyclic redundancy check) for error detection.
Conventional forward error correction includes use of a FEC encoder (such as BCH or LDPC in the transmitter to add parity bits. The parity bits are sent via suitable media, which may be a noisy data signal channel, along with a data packet. The corresponding receiver uses a matched FEC decoder and parity bits to correct errors introduced during transmission and to recover the data. (BCH codes form a class of cyclic error-correcting codes that are constructed using finite fields. Binary BCH codes that may be used to correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded by an algebraic syndrome decoding process which simplifies the decoder design using small low-power electronics. A low-density parity-check (LDPC) code is a linear error correcting code used in transmitting messages over noisy transmission channels and can allow the noise threshold to be set very close to the theoretical maximum for a symmetric memoryless channel.)
CRC code is widely used in digital receivers for error detection to detect errors caused by noise or interference occurring with corresponding “original” transmitted data signals. If a “CRC check” fails the CRC detection algorithm procedure because at least one data error is detected, a re-transmission by the transmitter is automatically requested. The message then is resent from the transmitter to the receiver until a CRC check “passes” CRC detection procedure with no detected data errors. CRC checks have been proposed for correcting single-bit errors in special circumstances, as indicated in the articles “Correcting single-bit errors with CRC8 in ATM cell header” (by Freescale Semiconductor Corporation), “Single Bit Error Correction Implementation in CRC-16 on FPGA” (by S. Shukla, N. Bergmann), and “CRC Lookup Table Optimization for Single Bit Error Correction” (by P. Yun).
CRC error detection is based on polynomial division. Specifically, a CRC code of length “n” is equal to the mathematical remainder of a message polynomial M(x) that is multiplied by a value xn and then is divided by a CRC generator polynomial G(x) of order n. In M(x), x is either a 1 or 0, corresponding to the message bit, and the exponent is the order or position of the message bit. An example of a CRC generator polynomial with n=24 isG(x)=x24+x10+x9+x6+x4+x3+x+1.If the division produces a remainder polynomial R(x), then R(x) is equal to the CRC code. The transmitter sends a message T(x)=M(x)×xn+R(x). (In other words, the CRC code is attached to the end of the message.) The associated receiver receives message T(x) along with any subsequently introduced error, which may be represented by an error polynomial E(x). If and only if E(x) is not divisible by G(x), the receiver declares the existence of an error which is represented by the error polynomial E(x).
Prior Art FIG. 1A shows a communication system including a conventional digital transmitter 26 and a conventional digital receiver 12. Digital transmitter 26 receives a data packet on a signal path 30 which is applied to the input of a CRC generation circuit 28. CRC generation circuit 28 generates a CRC code from the message bits and appends that CRC code to the message on signal path 30. The packet that is composed from the message and the CRC code is applied to an input of a digital transmitter baseband circuit 26-3 which performs the necessary modulation and possible channel coding. There typically is a mapping or transformation of the bits (i.e., 0's and or 1's) into “symbols” in transmitter digital baseband circuit 26-3. The output of digital transmitter baseband circuit 23-3 is applied to the input of a digital transmitter front end circuit 26-2 which includes various filters for meeting predetermined spectrum requirements. The output of digital transmitter front end circuit 26-2, which includes groups of bits (e.g., in hexadecimal format) representing the symbols, is applied to a digital to analog converter (DAC) 27, the output of which is coupled to an input of an RF analog transmitter circuit 26-1 which generates an RF signal representative of the information in the data packet, including the message, the appended CRC code, and any errors that have been introduced. The analog output of DAC 27 is input into transmitter RF analog circuit 26-1 which converts them to RF signals and transmits the RF signals via antenna 1. That is, the transmitter analog RF circuitry in block 26-1 modulates the analog output of DAC 27 to represent the analog information generated by DAC 27 in a high frequency RF format which then is transmitted via antenna 1 over the air or other suitable media.
Digital receiver 12 includes an RF analog receiver circuit 12-1 which receives the RF signal transmitted by digital transmitter 26 via receiver antenna 6 or other suitable media and then demodulates the received RF signal and applies the resulting demodulated signal to the input of an analog to digital converter (ADC) 29. The output of ADC 29 is applied to the input of a receiver digital front end circuit 12-2 which includes various noise-reducing filters. The output of receiver digital front end circuit 12-2 is applied to the input of a receiver digital baseband circuit 12-3 which performs demodulation of the signal received from digital baseband circuit 12-3 and possible channel decoding. Thus, the transmitted RF signal is received by antenna 6 of digital receiver 12, and the reverse of the functions performed by circuits 26-1, 26-2, 26-3 in digital transmitter 26 are performed in blocks 12-1, 12-2, and 12-3, respectively, of digital receiver 12. More specifically, the received RF signal is down-converted into an intermediate frequency (IF) signal which then passes through to various filters in receiver digital front end circuit 12-2 to reduce noise. Then the represented symbols are mapped or transformed to binary 1's and 0's by receiver digital baseband circuit 12-3. The foregoing circuitry and the transmission media may introduce errors into the digital information, so the information in the receiver digital baseband circuit 12-3 may be erroneous.
The output of receiver digital baseband circuit 12-3 is applied to the input of a CRC code verification circuit 14 which operates to calculate the CRC from the received message bits and compare a “received CRC code” with a “calculated CRC code”, and any mismatch indicates the existence of one or more errors in the received CRC bits being tested. The receiver 12 has “knowledge” of the “boundary” of the message and the appended CRC, either from the message length field embedded in the message or on the basis of a predetermined “agreement” between transmitter and receiver regarding the message length. If the “received CRC code” and the “calculated CRC code” match, the CRC check test is “passed”, and the entire data packet is sent for additional processing by a user application. However, if the calculated CRC code and the received CRC code do not match, i.e., if the CRC check test is “failed”, then CRC code verification circuit 14 automatically sends a request to transmitter 26 asking it to retransmit the original data packet.
Unfortunately, such retransmissions add delay to the communication, consume additional power in both the transmitter and receiver, and waste channel bandwidth. Furthermore, there typically is a limit to the number of the retransmissions that are allowed. When that limit is reached, the connection established between the transmitter and receiver may be terminated, in which case that connection would need to be restarted, thereby incurring further communication overhead between the transmitter and receiver. For example, in a BLE (Bluetooth low energy) system, if an error is detected the receiver automatically requests the transmitter to resend the data packet as indicated by reference numeral 11 in CRC code verification circuit 14 in Prior Art FIG. 1A.
The overhead of the prior art techniques (for example as shown in above-described FIG. 1A and subsequently described FIGS. 1B and 1C), in terms of delay, power consumed in the transmitter and the receiver, and limitation of channel capacity due to the above-mentioned retransmission of erroneously received packets detected by CRC, may be reduced by introducing error correction capability using the same CRC code that is originally for error detection. Nearly all systems that include a conventional digital transmitter and a conventional digital receiver (generally as shown in Prior Art FIG. 1A) include CRC code generation in both the transmitter and the receiver as part of any error detection system they may have. It should be appreciated that error “detection” involves determining if a received data packet includes any errors, but such error detection does not include “correction” of any errors that may be present in the received data packet.
A message includes a group of bits to be transmitted, and typically includes a “payload” and a control section called the “header” which includes information identifying the receiver and indicating how many bits are in the message. The payload is the message information intended to be received by a user or an application. The CRC code typically is appended or attached to the end of the message. (The term “message” is used herein to refer the bits that need to be sent from the transmitter to the receiver and the term “packet” or “data packet” is used to refer to the message along with the appended CRC. The message consists of the header and the payload.) The CRC code, or simply “CRC”, typically is generated as the remainder resulting from division of a message polynomial M(x) multiplied by a value xn and then divided by a CRC generator polynomial G(x). Typically, the CRC generator polynomial is a 16-bit, 24 bit, or 32 bit polynomial, depending on how “strong” or accurate the desired error detection capability should be, and may be generated using a linear feedback shift register LFSR. In Prior Art FIG. 1A, the entire data packet, including the appended CRC code, passes from CRC generator circuit 28 into transmitter digital baseband circuit 26-3.
Prior Art FIG. 1B shows a specific way of implementing both error detection and error correction in a receiver of a transmitter-receiver pair, and is a replica of FIG. 2 of U.S. Pat. No. 7,577,899 entitled “Cyclic Redundancy Check (CRC) Based Error Correction Method and Device” issued Aug. 18, 2009 to Nieto et al., and incorporated herein by reference. The following description of Prior Art FIG. 1B corresponds to the description of FIG. 2 in the Nieto et al. patent.
Referring to Prior Art FIG. 1B, the error detection and correction block 14 may include a CRC decoder 13 for performing the CRC and forwarding the M message bits to the output 16 if the CRC passes. If an error is detected, a “quality metric unit” 20 assigns a quality metric to each of the N message bits and M CRC bits, and error detection and correction block 14 may further include a comparator 24 to compare the assigned quality metrics to a threshold to select the K bits. The assigned quality metric may be based upon at least one of a Received Signal to Noise Ratio (RSNR) and a Forward Error Correction (FEC) confidence value, for example, provided by the input/receiver 12. The threshold or RSNR can be used to change the number of bits for correction.
Error detection and correction block 14 may include a memory 22 and/or table to store the possible bit error patterns which are preferably single-bit error patterns. Error detection and correction block 14 may determine whether a multiple-bit error has occurred in the N message bits and M CRC bits of the received message based upon at least the M CRC bits and further based upon a failure to match the CRC value with the single-bit error patterns. Error detection and correction block 14, via correction unit 15, corrects the single-bit errors based upon the single bit-error patterns, and corrects the multiple-bit errors based upon a logical combination of a plurality of single-bit error patterns. Single-bit errors may be corrected without reference to the K bits and quality metrics.
One aspect of Prior Art FIG. 1B is the pre-calculation of CRC bits for different single-bit error patterns. The total number of bits transmitted is N+M, N message bits plus M CRC check bits. An N+M element look-up table, e.g. in the memory 22, is used. The index of the look-up table is the position of the single error in the transmitted bit stream. The table element contains the M bit CRC check that would result at the receiver if a bit error was made at that position. The resulting received CRC is checked against all elements of the table to determine if the received bit stream is suffering from a single bit error in any of the positions. A more elaborate approach, described in the '899 patent, utilizes received bit quality metrics combined with the table to determine the most likely error patterns. Quality metrics for different bits that need to be corrected can be added together to determine the cost of correction, and with a comparison to a threshold, it can be determined whether the cost is too high. If so, the error pattern would not be corrected with the approach described herein.
Note that CRC error detection does not itself include error correction. In Prior Art FIG. 1B, the output of receiver 12 corresponds to the output of the receiver digital baseband circuit 12-3 in Prior Art FIG. 1A. The CRC decoder 13 in FIG. 1B decodes the CRC code that was transmitted by the transmitter, and compares it with a quality metric generated by quality metric unit 20. If there is a mismatch, then the system of FIG. 1B attempts to correct the detected error causing the mismatch. The quality metric takes that along with reliability information into account in comparing the received CRC code with the calculated CRC code to determine possible ways the error can occur. The comparison by comparator 24 in FIG. 1B is performed on the basis of groups of CRC code bits. If there is a match of the calculated and received CRC bits each time, it is assumed that the receiver received the bits correctly. Output block 16 can be a buffer that may contain the corrected digital output packet, and it may include multiple erroneous bits. If that is the case, correcting unit 15A reverses or “flips” the states of the erroneous bits, respectively, in order to make the needed corrections.
The technique of FIG. 1B (which is a copy of FIG. 2 of U.S. Pat. No. 7,577,889) relies on the quality metric associated with individual message bits in the digital receiver to identify possible error locations. Unfortunately, the quality metric is generally not a good indicator of error locations in modern digital receivers that typically utilize available maximum likelihood estimation types of algorithms in the demodulation process. As a result, error correction performance in the system shown in above described Prior Art FIG. 1B and described in U.S. Pat. No. 7,577,899 is quite limited.
For facilitating discussion of a system into which the subsequently described invention can be added, a system using the Bluetooth Low Energy standard is used as an example. (The present invention introduces a new way of using the existing CRC capability originally provided in the system transmitter for error detection to further accomplish error correction in the system receiver.) Those skilled in the art know that “Bluetooth” is a registered brand/trademark/certification mark for various wireless communication standards referred to herein as Bluetooth standards. The various Bluetooth standards have been developed and promulgated by the Bluetooth Special Interest Group known as “Bluetooth SIG”. The various brands/trademarks/certification marks are owned and licensed to various users by Bluetooth SIG., Inc. for use on and in conjunction with various communication devices. Up-to-date Bluetooth guidelines can be obtained from the Bluetooth SIG, Inc. website “https//www.bluetooth.org/en-us”. Proper authorized use of the Bluetooth brands, trademarks, and certification marks is enforced by Bluetooth SIG, Inc. to ensure that the standards are properly adhered to in accordance with the Bluetooth licensing terms and guidelines.
The Bluetooth Low Energy (BLE) brand/standard/certification mark is now called “Bluetooth Smart”. The standard called “Bluetooth 4.0” incorporates the BLE or Bluetooth Smart standard. The term “classic Bluetooth” is used herein to refer to all versions of the Bluetooth standards prior to Bluetooth 4.0. All of the Bluetooth standards are developed by building certification standards/programs around certain parts of the IEEE 802.15.x family of specifications.
A “piconet” is basically a collection of slave/advertisers that are scanned by a master/scanner that could wirelessly connect to another piconet. A “scatternet” is a type of ad-hoc computer network consisting of two or more piconets. The terms “scatternet and “piconet are typically applied to Bluetooth wireless technology. Bluetooth Low Energy (BLE) is a feature of Bluetooth 4.0 wireless radio technology aimed principally at low-power and low-latency applications for wireless devices with a short range, up to approximately 160 feet, and facilitates a wide range of applications.
“Prior Art” FIG. 1C shows a conventional BLE scatternet including a piconet A and a piconet B each including a “master” or “master/scanner” device capable of wireless communication with a number of nearby “slave” or “slave/advertiser” devices. Bluetooth low energy (BLE) is the lowest power standard, and using BLE for the advertising of slave devices in a piconet provides the lowest known power consuming mechanism within the BLE standard. If it is desired to have the lowest power radio standard presently available, BLE is considered to be the starting point.
In piconet A, master/scanner 3-1 is capable of wireless communication with advertisers 5-1, 5-2, 5-3, 5-4, and 5-5 through wireless links 2-1, 2-2, 2-3, 2-4, and 2-5, respectively. Similarly, in piconet B, master/scanner 10-2 is capable of wireless communication with/advertisers 5-6 and 5-7 through wireless links 2-6 and 2-7, respectively. Slave/advertiser 5-5 in piconet A also communicates with master 10-2 in piconet B through wireless link 7. In piconet A, master/scanner 3-1 can synchronize with any of the slave/advertisers in piconet A, for example as represented by reference numeral 15, to establish wireless link 2-1. After synchronization, master/scanner 3-1 then may perform two-way wireless data communication with the slave/advertiser, for example as represented by reference numeral 17.
In the prior art BLE systems in which each slave can generate a payload of a data packet and communicate with a single master or scanner, each slave typically also generates a CRC code that is included in the data packet. That CRC code is used for error detection, but a retransmission occurs every time an error is detected because no error correction is performed. This is inefficient from the viewpoints of power consumption and bandwidth. In addition, connection between the BLE slave unit and associated BLE master or scanner unit needs to be reestablished if such a retransmission also fails the CRC code check. Note that retransmission is costly in terms of power in both transmitter and receiver and in terms of increased delay. The delay is the amount of time from when the packet is first generated at the transmitter to the time the data packet is correctly received. Therefore, significant benefits could be achieved if it were possible and practical to introduce FEC capability into a BLE receiver using the CRC code that is already specified for error detection in the standard. Such benefits in speed/reliability performance and power reduction would save the substantial amount of RF power otherwise required for retransmissions by both the BLE masters and slaves.
In addition to BLE systems, there is in general an unmet need for a way to provide error correction capability in various communication systems including a transmitter and a receiver that may include error detection capability using CRC-based FEC error correction capability.
There also is an unmet need for a way to provide error correction capability in a communication system including a transmitter and a receiver that may include error detection capability but does not have CRC-based FEC error correction capability, without requiring a FEC encoder or a FEC decoder or circuitry for inserting extra parity bits into the transmitted data packets.
There also is an unmet need for a way to provide error correction capability in a communication system including a transmitter and a receiver that may include error detection capability but does not have CRC-based FEC error correction capability, without increasing the bandwidth of the communication system.
There also is an unmet need for a way to provide error correction capability in a communication system including a transmitter and a receiver that may include error detection capability but does not have CRC-based FEC error correction capability, without increasing system speed, and without increasing system power consumption.
There also is an unmet need for a way to provide error correction capability in a communication system including a transmitter and a receiver that may include error detection. capability but does not have CRC-based FEC error correction capability, and is suitable for use in a BLE communication system.
There also is an unmet need for a way to provide error correction capability in a communication system including a transmitter and a receiver that may include error detection capability but does not have CRC-based FEC error correction capability, without increasing latency due to message retransmissions necessitated by detected but uncorrected bit errors.